package leetcode.sort;

public class QuickSort extends AbstractSort {

    public QuickSort(int[] array) {
        super(array);
    }

    @Override
    protected void sort() {
        quick(0, array.length - 1);
    }

    private void quick(int left, int right) {
        if (left >= right) return;
        int mid = pivotIndex(left, right);
        quick(left, mid - 1);
        quick(mid + 1, right);
    }

    private int pivotIndex(int begin, int end) {
        // 备份选定的中轴元素
        int pivot = array[begin];
        while (begin < end) {
            // 先从右往左扫描进行比较
            while (begin < end) {
                if (pivot < array[end]) {
                    end--;
                } else {
                    array[begin++] = array[end];
                    break;
                }
            }
            // 再从左往右扫描进行比较
            while (begin < end) {
                if (pivot > array[begin]) {
                    begin++;
                } else {
                    array[end--] = array[begin];
                    break;
                }
            }
        }
        // begin == end退出循环
        // 将轴点元素放入最终的位置
        array[end] = pivot;
        // 返回轴点元素的位置
        return end;
    }
}
